package com.sheng.leetcode.year2022.month07.day21;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/07/21
 *
 * 814. 二叉树剪枝
 *
 * 给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
 * 返回移除了所有不包含 1 的子树的原二叉树。
 * 节点 node 的子树为 node 本身加上所有 node 的后代。
 *
 * 示例 1：
 * 输入：root = [1,null,0,0,1]
 * 输出：[1,null,0,null,1]
 * 解释：
 * 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
 *
 * 示例 2：
 * 输入：root = [1,0,1,0,0,0,1]
 * 输出：[1,null,1,null,1]
 *
 * 示例 3：
 * 输入：root = [1,1,0,1,1,0,1,0]
 * 输出：[1,1,0,1,1,null,1]
 *
 * 提示：
 *
 * 树中节点的数目在范围 [1, 200] 内
 * Node.val 为 0 或 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-pruning
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0814 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(1);
//        TreeNode right = new TreeNode(0);
//        right.left = new TreeNode(0);
//        right.right = new TreeNode(1);
//        root.right = right;

//        TreeNode root = new TreeNode(1);
//        TreeNode left = new TreeNode(0);
//        left.left = new TreeNode(0);
//        left.right = new TreeNode(0);
//        TreeNode right = new TreeNode(1);
//        right.left = new TreeNode(0);
//        right.right = new TreeNode(1);
//        root.right = right;

        TreeNode root = new TreeNode(0);
        TreeNode right = new TreeNode(0);
        right.left = new TreeNode(0);
        right.right = new TreeNode(0);
        root.right = right;
        TreeNode treeNode = new Solution().pruneTree(root);
        System.out.println(treeNode);
    }

}

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        //我需要一个方法，判断该子树结点值是否全为0，及是否需要进行修剪
        if (prune(root)) {
            root = null;
        }
        return root;
    }

    public boolean prune(TreeNode tree) {
        //该节点为空
        if (tree == null) {
            return true;
        }
        //该节点为叶子结点
        if (tree.val == 0 && tree.left == null && tree.right == null) {
            return true;
        } else {
            boolean flag1 = false, flag2 = false;
            //判短该结点的左结点是否满足条件，满足条件则进行修剪
            if (prune(tree.left)) {
                tree.left = null;
                flag1 = true;
            }
            //判短该结点的右结点是否满足条件，满足条件则进行修剪
            if (prune(tree.right)) {
                tree.right = null;
                flag2 = true;
            }
            //当该结点的左结点，右结点以及本事val值为0时，该结点需要被修建
            if (tree.val == 0 && flag1 && flag2) {
                return true;
            } else {
                //否则不修剪
                return false;
            }
        }
    }
}
